package com.example.designpatterns.iterator.advanced;

import com.example.designpatterns.iterator.Iterator;
import java.util.Stack;

/**
 * 中序遍历迭代器
 * 遍历顺序：左子树 -> 根节点 -> 右子树
 * @param <T> 元素类型
 */
public class InOrderIterator<T extends Comparable<T>> implements Iterator<T> {
    private TreeCollection<T> treeCollection;
    private Stack<TreeCollection.TreeNode<T>> stack;
    private TreeCollection.TreeNode<T> current;
    
    /**
     * 创建中序遍历迭代器
     * @param treeCollection 二叉树集合
     */
    public InOrderIterator(TreeCollection<T> treeCollection) {
        this.treeCollection = treeCollection;
        this.stack = new Stack<>();
        this.current = treeCollection.getRoot();
        
        // 将左侧节点全部入栈
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
    }
    
    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    @Override
    public T next() {
        if (!hasNext()) {
            return null;
        }
        
        // 取出栈顶节点
        TreeCollection.TreeNode<T> node = stack.pop();
        T result = node.value;
        
        // 处理右子树
        current = node.right;
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        return result;
    }
} 